package com.wenhai.leetcode.tree;

import java.util.TreeMap;

/**
 * https://leetcode-cn.com/problems/map-sum-pairs/
 *
 * @author wenhai
 * @date   2021/3/26
 */
public class _677键值映射 {
    private Node root;
    /** Initialize your data structure here. */
    public _677键值映射() {
        this.root = new Node();
    }

    public void insert(String key, int val) {
        Node cur = this.root;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        cur.val = val;

    }

    public int sum(String prefix) {
        Node cur = this.root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null) {
                return 0;
            }
            cur = cur.next.get(c);
        }
        return sum(cur);

    }

    private int sum(Node node) {
        int sum = node.val;
        if (node.next == null) {
            return sum;
        }

        for (char c : node.next.keySet()) {
            sum += sum(node.next.get(c));
        }
        return sum;
    }



    private class Node {
        int val;
        TreeMap<Character, Node> next;

        public Node() {
            this(0);
        }

        Node(int val) {
            this(val, new TreeMap<>());
        }

        Node(int val, TreeMap<Character, Node> next) {
            this.val = val;
            this.next = next;
        }
    }
}
